package cn.edu.jxau.test;

import java.util.Arrays;

public class Sort {

    public static void main(String[] args) {

        int[] arr = { 31, 55, 76, 24, 67, 89, 23, 90, 67, 54, 97, 39, 26, 99, 43, 65, 35 };
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔排序：对数组的局部进行排序，不断扩大局部的范围，这个过程也是整个数组有序程度增加的过程，
     * 最终用插入排序排序整个数组。
     * 
     * 1.对插入排序的改进，可以应付大规模的数组
     * 2.递增序列的选择会影响希尔排序的效率
     * @param arr
     */
    private static void sort(int[] arr) {

        int span = 1; // 递增序列
        while (span < arr.length / 3) {
            span = span * 3 + 1;
        }
        while (span >= 1) {
            
            for(int i=span;i<arr.length;i++) {
                int j = i;
                int temp = arr[j];
                while(j-span>=0 && temp<arr[j-span]) {
                    arr[j] = arr[j-span];
                    j-=span;
                }
                arr[j] = temp;
            }
            span /= 3;
        }
    }
}
